1. Field of Invention
The concept of the invention relates to an improved, special purpose data processor or hard wired type or microprogrammed microprocessor-based fast fourier transform (or other periodic function) analyzer.
2. Description of the Prior Art
In the field of data processing by digital machine means, the analysis of the periodic function properties of data specimens is frequently required. Such data may be in the form of binary-coded image signals corresponding to an image field pattern of interest, while the occurrence therein of selected bandwidths of spatial frequencies may correspond to (or identify) preselected features of interest in such image field pattern. Use of a two-dimensional generalized sequency analyzer, such as a fast fourier transform (2D-FFT) machine or the like may be employed for an automatic machine method of such identification, as described in co-pending U.S. Application Ser. No. 960,813, filed Nov. 15, 1978, (now U.S. Pat. No. 4,225,850) entitled NON-FINGERPRINT REGION INDICATOR and assigned to Rockwell International Corporation, assignee of the subject application. Such prior art machines for performing such operation of generalized sequency operation or fast fourier transform determination have generally been suitably programmed general purpose machines such as the IBM 7094, Burroughs B5500, CDC 6400 and CDC 6600 type machines, as described more fully in the above-noted co-pending U.S. Application Ser. No. 960,813, filed Nov. 15, 1978. Such large-scale machines have adequate computing capacity and speed to perform the fast fourier transform, when appropriately programmed with a suitable algorithm as indicated in the volume, Digital Data Processing, edited by Rabiner and Rader, published by the IEEE press (1972). Such commercially available machines are, however, too large, expensive and impractical to use in the special purpose data processing and control applications which require to be dedicated to such generalized sequency analysis, such as the fast fourier transform. The initial cost of acquisition and continuing maintenance costs of such general purpose machines are all out of proportion to the limited computational employment to be made thereof in a dedicated or special purpose application of generalized sequency analysis, while the bulk of such machines precludes their installation in the limited accommodations generally available for such special purpose application, including mobile accommodations. Further, although such bulk, complexity and associated costs are deplored, yet the classical algorithms employed in implementing such applications have limited the use of smaller machines including special purpose machines dedicated to or especially adapted for performing the fast fourier transform. An example of a special purpose analog machine for both calculation of a signal (and also the frequency domain equalization of such signal) is taught in U.S. Pat. No. 4,106,103 to Perreault for DEVIATION OF DISCRETE FOURIER TRANSFORM COMPONENTS OF A TIME DEPENDENT SIGNAL.
In the digital fast fourier processing of sampled time history of say N samples over the sampled signal epoch of interest, successive samples are treated as complex quantities and are organized as two groups of sequences, each occurring in a mutually exclusive one of a first half and second half (A and B) of the sampled epoch. As is more fully explained in U.S. Pat. No. 4,158,888 to Shapiro for FAST FOURIER TRANSFORM PROCESSOR USING SERIAL PROCESSING AND DECODER ARITHMETIC AND CONTROL SECTION, the FFT processor may be characterized as a digital processor which repetitively performs the basic computations AW+B and AW-B, where A and B are complex digital words, each corresponding to a different one of N digital samples to be analyzed, and W is a complex digital word corresponding to a weighting function. Mechanization involves use of a scalar multiplier to provide components of the complex product AW, storage means to store such product, and an adder/subtractor for combining such stored product to generate the complex product AW and to combine this complex product with the components of the complex variable B.
Detailed arithmetic processing of the sequential computations in a sequency analyzer of FFT machine, as a practical matter, involves reorganizing the discrete fourier transform data matrix into submatrices, each of which requires simpler arithmetic operations, and the results of which simpler operations may be merely simply combined, rather than multiplied. Such reorganization process is referred to generically as decimation, the two classical methods of reorganizing the data matrix being referred to as decimation-in-frequency and decimation-in-time. The basic resultant computational operation is called a "butterfly".
What is desired is a hard wired special purpose machine for performing the butterfly computation in a yet more efficient manner, as to involve still fewer steps and arithmetical sequences, as to also be smaller, less complex, less costly and more reliable.
The above-noted U.S. Pat. No. 4,158,888 to Shapiro is addressed to the decimation-in-time technique, and employs a serial-parallel multiplier for providing the product AW and a data decoder 68 for effecting the decimation-in-time butterfly which is to generate the combination A.sup.+ =AW+B and B+=AW-B where these quantities are complex variables, By means of response to a sequence of clock control signals, a decoder section 60 (which includes data decoder 68) serves to control the performance of a serial-parallel multiplier in cooperation with a random access memory.
By means of serial storage and retrieval of the scaled signals AW in response to a sequence of clock-control signals, a simplified data decoder may be thus employed to effect both the combination of AW and B, as well as to perform other functions. In other words, the decimate-in-time type system of Shapiro employs a clock control element 52 (in Shapiro's FIG. 5) to effect mode control of multi-mode or time-shared computing elements in cooperation with a random access memory (RAM) to perform all the classical calculations shown in Table 8 of such reference.
Such mechanization of Shapiro, employing serial storage and retrieval of signals to be scaled via a classical serial-parallel multiplier to effect the product AW, and further employing a data decoder and shift register (as a serial adder function) to algebraically combine the terms AW and B, further involves serial storage and retrieval of all of his data as to require a substantial processing time:
2.[.3[M+N-1]+(N+1).]. bits where:
M=number of bits per input to multiplier 72 from multiplier coefficient decoder 64 PA0 N=number of bits per input to multiplier 72 from multiplier control decoder 66 PA0 (M+N-1)=number of bits of product formation (AW) time from the output of multiplier 72 PA0 (N+1)=number of bits to form B.sub.R or B.sub.I PA0 3=number of passes through the Butterfly or calculation repetitions PA0 3[M+N-1]+(N+1)=number of bit times to form either the real or imaginary component of AW PA0 2.[.3[M+N-1]+(N+1).].=the number of bit times to form the complex sum AW+B.
Thus, while Shapiro teaches a FFT analyzer for application to real time processing of doppler data, the inherent speed limitation of such serial data storage and retrieval type of processing ultimately limits the number of discrete frequencies which can be handled by a given machine as to represent a limitation in either bandwidth or resolution, or at least a trade-off between them.